

# 递归实现欧几里得算法
# 输入值a,b都为整数，
# 返回值为a,b的最大公约数
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# 递归实现扩展欧几里得算法
# 输入值a,b都为整数，保证a不小于b
# 返回三个值，第一个为最大公约数，第二个为x，第三个为y
# 满足： ax + by = (a,b)


def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x1, y1 = exgcd(b, a % b)
        x = y1
        y = x1-(a//b)*y1
        return d, x, y

# 使用扩展欧几里得算法求拟
# 输入值a,b都为整数，保证a不小于b
# 返回值，第一个为是否有逆，第二个为逆x的值
# 满足： ax = 1 mod b


def inv(a, b):
    d, x, y = exgcd(a, b)
    if d == 1:
        # 有逆
        while x < 0:
            x = x + b
        return True, x
    else:
        # 无逆
        return False, -1


# 迭代求最大公约数
def gcd1(a, b):
    if a < b:
        a, b = b, a
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return b


d = gcd(63, 28)
print("%d" % d)

a = 12
b = 7
r1, r2, r3 = exgcd(a, b)
print("%d %d %d" % (r1, r2, r3))

r1, r2 = inv(a, b)
print("%d %d" % (r1, r2))
